# LeetCode 37、解数独

# 一、题目描述

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

img

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 解数独（LeetCode 37）：https://leetcode.cn/problems/sudoku-solver/
class Solution {
    public void solveSudoku(char[][] board) {

        // 回溯算法
        backTrace(board , 0 , 0 );

    }

    // board : 二维矩阵
    // row   : 第几行，从 0 开始计数  
    // col   : 第几列，从 0 开始计数
    private boolean backTrace(char[][] board, int row, int col) {

        // 递归终止条件
        // 最后一行已经填充完了所有数字，来到了第 board.length 行
        // 由于 row 是从 0 开始计数，说明此时 board 里面的每一行都已经填充好数字
        // 获取到结果了 
        if( row == board.length ) return true;

        // 如果当前行的最后一列也遍历完毕，开始从下一行的第一列（索引为 0 的位置）开始
        if( col == board.length ) return backTrace( board , row + 1 , 0 );

        // 如果当前位置已经有数字了，那么直接处理下一个位置，即当前这一行的下一个列
        if( board[row][col] != '.') return backTrace(board , row ,col + 1);

        // 经过上面三个判断，当前位置终于可以开始填数字了
        // 每个位置可以填充的数字都能从 1 到 9 进行选择
        for( char i = '1' ; i <= '9' ; i++){

            // 填充过程中需要判断填充的数字是否遵循了 3 个规则
            // 如果发现不遵循，也就无法继续填充后面的数字了
            // 需要考虑在当前位置填充另外一个数字，i 调整为 i + 1 即可
            if( !isValid(board , row , col , i )) continue;

            // 否则，说明填充的数字 i 符合【目前】的要求
            // 把它填充到 board[row][col]
            board[row][col] = i;

            // 开始考虑下一个位置的填充情况了
            // 由于是一行行、一列列去填充，下一个位置是 col + 1 的位置
            // 只有它能保证正确填充，当前这个位置填充的 i 才是正确
            if( backTrace( board ,row ,col  + 1)) return true;

            // 否则，当前这个 i 只是符合了【目前】的要求，不符合全部的要求
            // 于是，这个位置不能填 i ，还原为空白格再继续分析下去
            board[row][col] = '.';
    
        }

        return false;

    }

    // 判断当前位置是否遵循数独的 3 个规则
    private static boolean isValid(char[][] board, int row, int col, char c) {

        for (int i = 0; i < 9; i++) {

            // 1、数字 1-9 在每一行只能出现一次
            // 判断当前这一行是否已经有 c 这个数字存在
            if (board[row][i] == c)
                return false;

            // 2、数字 1-9 在每一列只能出现一次
            // 判断当前这一列是否已经有 c 这个数字存在
            if (board[i][col] == c)
                return false;
            
            // 3、数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
            // 判断当前这个九宫格是否已经有 c 这个数字存在
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
                return false;
        }
        // 如果遵循了这 3 个规则
        // 说明可以填充 c 这个数字
        return true;
    }
}

# 2、C++ 代码

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        backTrace(board, 0, 0);
    }

    bool backTrace(vector<vector<char>>& board, int row, int col) {
    if (row == board.size()) return true;
    if (col == board[0].size()) return backTrace(board, row + 1, 0);
    if (board[row][col] != '.') return backTrace(board, row, col + 1);

    for (char c = '1'; c <= '9'; c++) {
        if (isValid(board, row, col, c)) {
            board[row][col] = c;
            if (backTrace(board, row, col + 1)) return true;
            board[row][col] = '.';
        }
    }

    return false;
    }

    bool isValid(vector<vector<char>>& board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == c) return false;
            if (board[i][col] == c) return false;
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
        }

        return true;
    }

};

# 3、Python 代码

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.backTrace(board , 0 , 0 )

    # board : 二维矩阵
    # row   : 第几行，从 0 开始计数
    # col   : 第几列，从 0 开始计数
    def backTrace(self, board: List[List[str]], row: int, col: int) -> bool:

        # 递归终止条件
        # 最后一行已经填充完了所有数字，来到了第 board.length 行
        # 由于 row 是从 0 开始计数，说明此时 board 里面的每一行都已经填充好数字
        # 获取到结果了
        if row == len(board):
            return True

        # 如果当前行的最后一列也遍历完毕，开始从下一行的第一列（索引为 0 的位置）开始
        if col == len(board):
            return self.backTrace(board, row + 1, 0)

        # 如果当前位置已经有数字了，那么直接处理下一个位置，即当前这一行的下一个列
        if board[row][col] != '.':
            return self.backTrace(board, row, col + 1)

        # 经过上面三个判断，当前位置终于可以开始填数字了
        # 每个位置可以填充的数字都能从 1 到 9 进行选择
        for i in range(1, 10):
            # 填充过程中需要判断填充的数字是否遵循了 3 个规则
            # 如果发现不遵循，也就无法继续填充后面的数字了
            # 需要考虑在当前位置填充另外一个数字，i 调整为 i + 1 即可
            c = str(i)
            if not self.isValid(board, row, col, c):
                continue

            # 否则，说明填充的数字 i 符合【目前】的要求
            # 把它填充到 board[row][col]
            board[row][col] = str(i)

            # 开始考虑下一个位置的填充情况了
            # 由于是一行行、一列列去填充，下一个位置是 col + 1 的位置
            # 只有它能保证正确填充，当前这个位置填充的 i 才是正确
            if self.backTrace(board, row, col + 1):
                return True

            # 否则，当前这个 i 只是符合了【目前】的要求，不符合全部的要求
            # 于是，这个位置不能填 i ，还原为空白格再继续分析下去
            board[row][col] = '.'

        return False

    # 判断当前位置是否遵循数独的 3
    def isValid(self,board: List[List[str]], row: int, col: int, c : str):
        for i in range(9):
            if board[row][i] == c:
                return False
            if board[i][col] == c:
                return False
            if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == c:
                return False
        return True

← LeetCode 37、解数独（位运算法） LeetCode 1020、飞地的数量 →

# LeetCode 37、解数独

# 一、题目描述

# 二、题目解析

# 三、参考代码

# 1、Java 代码

# **2、**C++ 代码

# 3、Python 代码

# 2、C++ 代码